package com.hwk.leetcode.leet206反转链表;


public class Solution {
    public ListNode reverseList1(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode newHead = this.reverseList1(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }

    public ListNode reverseList2(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }

        ListNode newHead = null;
        while (head != null){
            ListNode tmp = head.next;
            head.next = newHead;
            newHead = head;
            head = tmp;
        }

        return newHead;
    }

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        ListNode listNode4 = new ListNode(4);
        ListNode listNode5 = new ListNode(5);

        listNode2.next = listNode1;
        listNode3.next = listNode2;
        listNode4.next = listNode3;
        listNode5.next = listNode4;

        System.out.println(listNode5);

        Solution solution = new Solution();
        ListNode listNode = solution.reverseList1(listNode5);

        System.out.println(listNode);
    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}